package com.leetcode.partition11;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/29 10:57
 */
public class LC1005K次取反后最大化数组和 {

    public static int largestSumAfterKNegations(int[] nums, int k) {
        return greedy(nums, k);
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 3, -5};
        int k = 2;
        System.out.println(largestSumAfterKNegations(nums, k));
    }

    private static int greedy2(final Integer[] nums, int k) {
        Arrays.sort(nums, (o1, o2) -> Math.abs(o1) - Math.abs(o2));
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        if (k % 2 == 1) nums[nums.length - 1] *= -1;
        int answer = 0;
        for (int i = 0; i < nums.length; i++) answer += nums[i];
        return answer;
    }

    private static int greedy(final int[] nums, int k) {
        Arrays.sort(nums);
        int answer = 0;
        int minPositiveIndex = -1;
        //尽量对负数进行操作，如果没有负数，则对小的正数进行操作
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
                minPositiveIndex = i;
            } else if (nums[i] == 0) {
                k = 0;          //数组操作全部消耗在0上
            } else {
                int index = i;
                if (minPositiveIndex != -1 && nums[minPositiveIndex] < nums[i]) {
                    index = minPositiveIndex;
                }
                //nums[index]是最小的一个正数
                if (k % 2 != 0) nums[index] = -nums[index];
                k = 0;
                break;
            }
        }
        while (k != 0) {
            if (k % 2 != 0) nums[nums.length - 1] = -nums[nums.length - 1];
            break;
        }
        for (int i = 0; i < nums.length; i++) {
            answer += nums[i];
        }
        System.out.println(Arrays.toString(nums));
        return answer;
    }
}
